#include "vm/frame.h"
#include <stdlib.h>

#include "filesys/file.h"
#include "threads/malloc.h"
#include "threads/palloc.h"
#include "threads/synch.h"
#include "threads/thread.h"
#include "userprog/pagedir.h"
#include "userprog/syscall.h"
#include "vm/page.h"
#include "vm/swap.h"
#include "threads/interrupt.h"

// frame table initialization
struct semaphore frame_sema;
void frame_table_init(void)
{
    // only init once
    if (frame_initialization == true)
    {
        return;
    }
    frame_initialization = true;

    list_init(&frame_table_list);
    lock_init(&frame_table_lock);
    lock_init(&eviction_lock);
    sema_init(&frame_sema, 1);
}

/*
Returns the new page directory, or a null pointer if memory
allocation fails.
*/
void *
frame_allocate(enum palloc_flags flag)
{
    uint8_t *pd = palloc_get_page(flag);
    if (pd != NULL)
    { // palloc success

        // add a new frame table entry
        struct frame_table_entry *fte = malloc(sizeof(struct frame_table_entry));

        fte->page = pd;
        fte->owner = thread_current();

        if (!lock_held_by_current_thread(&frame_table_lock))
        {
            lock_acquire(&frame_table_lock);
        }
        list_push_back(&frame_table_list, &fte->elem);
        lock_release(&frame_table_lock);
    }
    else
    {
        while (pd == NULL)
        {
            evict();
            pd = palloc_get_page(flag);
        }
        ASSERT(pd);
        struct frame_table_entry *fte = malloc(sizeof(struct frame_table_entry));
        fte->page = pd;
        fte->owner = thread_current();
        lock_acquire(&frame_table_lock);
        list_push_back(&frame_table_list, &fte->elem);
        lock_release(&frame_table_lock);
    }
    return pd;
}

// free this frame
void frame_free_page(void *some_page)
{
    struct frame_table_entry *frame_to_free = frame_find_page(some_page);

    lock_acquire(&frame_table_lock);
    if (frame_to_free != NULL)
    { // found the frame
        list_remove(&frame_to_free->elem);
        palloc_free_page(frame_to_free->page);
        // sema_up(&frame_sema);
    }
    lock_release(&frame_table_lock);
}

// find the frame in frame list
struct frame_table_entry *
frame_find_page(void *some_page)
{
    struct list_elem *e;

    for (e = list_begin(&frame_table_list); e != list_end(&frame_table_list);
         e = list_next(e))
    {
        struct frame_table_entry *fte = list_entry(e, struct frame_table_entry, elem);
        if (fte->page == some_page)
        {
            return fte;
        }
    }
    return NULL;
}

// evict a page
bool evict()
{

    bool eviction_success = false;
    struct frame_table_entry *victim_frame;
    victim_frame = choose_a_victim_fifo();
    if (victim_frame == NULL)
        return false;
    struct s_page_table_entry *victim_s_pt_entry = frame_table_entry_to_s_pt_entry(victim_frame);
    ASSERT(victim_s_pt_entry != NULL);
    struct thread *owner_thread = victim_frame->owner;
    size_t index;
    index = swap_out_of_memory(victim_s_pt_entry->upage);
    pagedir_clear_page(owner_thread->pagedir, victim_s_pt_entry->upage);
    list_remove(&victim_frame->elem);
    palloc_free_page(victim_frame->page);
    victim_s_pt_entry->is_in_memory = false;
    victim_s_pt_entry->type = PAGE_IN_SWAP;
    victim_s_pt_entry->swap_index = index;
    return true;
}

/*
find the s_page_table_entry mapped with frame_table_entry
return the s_page_table_entry.
*/
struct s_page_table_entry *
frame_table_entry_to_s_pt_entry(struct frame_table_entry *ft_entry)
{
    struct s_page_table_entry *s_pt_entry;
    struct thread *owner_thread;

    owner_thread = ft_entry->owner;

    struct list *s_page_table = &owner_thread->s_page_table;

    struct list_elem *e;
    for (e = list_begin(s_page_table); e != list_end(s_page_table); e = list_next(e))
    {
        s_pt_entry = list_entry(e, struct s_page_table_entry, elem);
        uint32_t *kpage = pagedir_get_page(owner_thread->pagedir, s_pt_entry->upage);
        // printf("%x %x\n", kpage, ft_entry->page);
        if (kpage == ft_entry->page)
        {
            return s_pt_entry;
        }
    }
    return NULL;
}

struct frame_table_entry *
choose_a_victim_fifo()
{
    struct frame_table_entry *victim_frame;
    struct list_elem *e;
    lock_acquire(&frame_table_lock);
    for (e = list_begin(&frame_table_list); e != list_end(&frame_table_list); e = list_next(e))
    {
        victim_frame = list_entry(e, struct frame_table_entry, elem);
        if (victim_frame->owner == thread_current())
        {
            lock_release(&frame_table_lock);
            return victim_frame;
        }
    }
    lock_release(&frame_table_lock);
    return NULL;
}

// clear the frame of a thread
void clear_frame_with_owner(struct thread *t)
{
    struct list_elem *e = list_begin(&frame_table_list);
    while (e != list_end(&frame_table_list) && e != NULL)
    {
        struct frame_table_entry *fe = list_entry(e, struct frame_table_entry, elem);

        if (fe != NULL && fe->owner == t)
        {
            lock_acquire(&frame_table_lock);
            e = list_remove(e);
            palloc_free_page(fe->page);
            free(fe);
            lock_release(&frame_table_lock);
            if (e == NULL)
                break;
        }
        else if (e != NULL && e->next != NULL)
        {
            e = list_next(e);
        }
        else
        {
            break;
        }
    }
}